1. Field of the Invention
The invention relates to data integrity in applications employing smartcards, in particular smartcards in connection with remote stations like personal or desktop card readers or similar inexpensive terminals. In such applications, unless properly handled, any interruption of a data transfer between the smartcard and a terminal can result in making the smartcard unusable and/or corrupt the data, any of which in turn often greatly affects the user.
2. Background
Smartcards today have many different uses of which the use in the financial and banking field is a prominent one. In this field, the data integrity issue is of particular importance since personal financial data are usually highly sensitive and a failing smartcard may, at times, present a significant problem.
Data integrity in the context here means error-free data transmission between a data source or receiver and the smartcard, an error-free record of the occurred transmission and consistent data on both sides giving an accurate, uncorrupted picture of the transaction that has occurred, whether completed or not. Data corruption may be caused by various events: a line breakdown to the terminal, a power failure, human interactionxe2x80x94e.g. someone removes the smartcard from a terminalxe2x80x94or even intentionally by a fraudulent attempt.
Whereas normal software techniques may guarantee the validity of the data content through secure messaging protocols and the appropriate realization in the smartcard, situations may occur where the traditional methods do not successfully work. One of the potential threats, as mentioned above, is the power loss situation. While the smartcard alters data in its memory, it may reach states where the data to be modified is lost, neither the old value nor the new value is available after the power loss. Furthermore the smartcard can be in a state where only a restricted functionality is available or, worst case, the card does not work at all. While there are other exposures to the card which may scratch the data, e.g. temperature exposure, mechanical break, electromagnetic radiation, the power loss situation, no matter whether by intent of the user or not, is the most probable threat which may occur.
From the field of database systems, different approaches to solve these problems are already known. Generally, a database (like a smartcard can be regarded as) has to xe2x80x9cknowxe2x80x9d only two states which may be defined as before changes and after changes caused by a transaction. Any other situation must be avoided. Database technology has defined the terms commitment and atomicity in this respect. A data commitment is an external trigger which tells the database that the data being submitted is complete and therefore is relevant to change the content of the database. Atomicity describes the idea that only two states (before and after) can exist. If a database guarantees the atomicity of a transaction, then it has a technical functionality to guarantee only these two states. In the following, some of the techniques known today shall be described and some of the used terms explained.
For a better understanding, the term atomic transaction shall be explained in some detail. An atomic transaction is any computerized transaction, e.g. banking or reservation transaction, that appears to be instantaneous and indivisible in the sense that it either runs to successful completion or completely fails, leaving no trace in any computer, as if it has never started. The concept was formulated to deal with transactions such as bank transfers, which involve multiple information updates, e.g. subtracting money from one account A and then adding it to another account B, yet should not be interrupted by failures of a computer or network, or by conflict with other transactions taking place in between the update operations. The main reason is that this could leave the affected database records in an inconsistent state, e.g. money debited from A but not credited to B or vice versa.
All existing database and transactions processing systems (e.g. IBM""s DB2 database system as well as others) implement a variety of mechanisms for making such transactions atomic, i.e. for allowing to roll them back without a trace or to force them to a successful completion in spite of inevitable failures or conflicts. Known techniques as Write-Ahead Logs (WAL), Intention Lists (ILs), Commit Records (CRs), Two-Phase Commit Protocols (TPCP) in distributed systems, etc., are documented in any classical textbook on the subject, e.g. P. A. Janson: Operating Systems Structures and Mechanisms, Academic Press, Inc., London, 1985, pp.175 et seq. An earlier reference is by W. H. Kohler: A Survey of Techniques for Synchronization and Recovery in Decentralized Computer Systems, ACM Computing Surveys 13, Vol. 2, pp. 149-184.
Here, data being modified is written into a buffer separate from the database, the Write Ahead Log. Beside the data, additional information is available in this log related to the correct address where the data has to be placed into. The log is marked invalid during this time. When the data modification is committed, the log will be marked valid. The data contained in the log is now written to the database. If all data was written out of the log, it is marked invalid again.
If a power failure occurs while data is written into the Write Ahead Log, the system will find the Buffer invalid and the data will remain at the same state as before, i.e. prior to the update.
If a power failure occurs when the Write Ahead Log is valid, then the whole Log or at least all entries which have not been assigned as written will be transferred to the database. Multiple power failures during this phase will never stop the update of the database until the final new state is reached. The database will, then end always in the committed and updated state.
Another method which is just the inverse of the Write Ahead Log, is the Backtracking method. Again, a separate buffer, the Backtrack Buffer, is used. However, data being modified is written directly to the database, after the xe2x80x9coldxe2x80x9d data has been written to the Backtrack Buffer. Using this method, each such xe2x80x9cbackupxe2x80x9d entry has to be marked valid individually after it has been written; then the new data is written to the database. When the input data is committed, the Backtrack Buffer is declared invalid. All backup entries are then discarded.
The advantage of this method is that the new data is earlier available in the database and does not have to be locked until the data input is committed.
If the power fails while the Backtrack Buffer is being written, all valid entries of the Backtrack Buffer will be rewritten to the database in order to bring the database back to the xe2x80x9coldxe2x80x9d state. If the power fails while new data is written to any database location, the appropriate backup data will be tagged as valid. Therefore, the data location will be restored with the old backup data on the next power bring-up. The data base will also end up with the xe2x80x9coldxe2x80x9d state. If the power fails after the commitment, the backup buffer is declared invalid and the new data content will remain in the database.
Small data bases typically have a duplicated xe2x80x9cshadowxe2x80x9d of the actual database, e.g. RAID systems in a server environment. There, the Write Ahead or Backtrack Buffers are replaced by a full spare data base, which serves as spare in case of a disaster other than a power failure, e.g. in case of a head crash on fixed disks. There are several possible solutions to synchronize this shadow database with the master database. Generally it can be said that those approaches are not relevant to smartcards because of their limited memory size.
A modified scheme of the above described Write Ahead or Backtrack Buffer techniques is the idea to use a xe2x80x9csparexe2x80x9d entry in a database. A list might have a particular number of rows plus one spare row. Whenever new data comes in, it will be written to the spare location. After the data is committed, the xe2x80x9coldxe2x80x9d row will be declared as spare while the previous spare row will get the index of the updated row.
If the power fails while data is written to the spare row, the database will not see any alteration after being repowered. If the power fails after the vector swapping, the new data is available in the previous spare row and the references are set to this row. The new state is found. Thus, the commitment problem is reduced to the correct swapping of the vectors.
Certainly the swap of the vectors has to be made using atomic transaction schemes. The main advantage of this method is that it is very fast, as only the index information has to be swapped instead of copying the data twice. The disadvantage is the more complicated structural topology, which requires one spare row on each table as explained in the above example.
For a number of reasons, the concept of such atomic transactions and the need to protect transactions with suitable logic has not yet been applied to smartcard systems. Some of the reasons shall be explained herein below.
First, practically all smartcard operating systems have been strictly sequential programs and thus obviated the need to protect against parallelism. In other words, since there wasxe2x80x94and still isxe2x80x94no parallel execution of any processes, protection against any interference between simultaneous or nearly simultaneous processes appeared unnecessary.
Second, smartcards were used so far mainly in conjunction with ad-hoc, industry-specific, on-line; often rugged acceptance devices, mostly card readers, which devices tightly control the environment while in operation. The probability of such devices failing during a card operation is rather small, in particular since they usually keep the card within a closed and secure environment during processing and avoid uncontrolled user interaction. An example of such devices are bancomats which keep the smartcard within the machine, i.e. out of reach of the customer, as long as processing takes place.
Hence atomicity accidents have not been an issue until now, and the need for atomicity protection has not been explicitly recognized. However, the recent emergence of low-cost, consumer-quality, hand-held readers for personal use and of simple desktop readers for the supermarket environment, to name just two, where the operational environment does not offer any protection against user interference or power supply failures, changes the boundary conditions and makes the need to protect card operations an absolute requirement.
A further and perhaps more important aspect is that there are at least two significant differences between a smartcard and a classical computer system making the straightforward application or adaptation of known atomicity solutions to the smartcard environment practically impossible.
First, after a failure, a classical transaction system will spontaneously try to reconnect to its environment, figure out whether anything got interrupted and either back out of it or complete it as may be appropriate. This assumption cannot be made for smartcards. If a card operation is interruptedxe2x80x94e.g. because the user removed the card from the reader, thus cutting power supplyxe2x80x94there is absolutely no guarantee that the user will ever reinsert it into a reader, let alone into the same reader, to complete or roll back the interrupted operation. For all practical purposes, the user knows nothing about atomic transactions and is not even aware that he or she interrupted anything critical. Thus, any concept or design assuming automated recovery after a failure will not work.
Second, classical transactions systems usually have ample computing resources and few environmental constraints to implement the necessary atomicity protection and recovery mechanisms. This is not the case for smartcards. They have very limited space and processing power and must further cope with nonvolatile memory technologies that allow updating any given memory location only a limited number of timesxe2x80x94around 10 000 now, but going on to 100 000 times with today""s technology.
In a pay-per-view TV environment, i.e. in a quite different field, U.S. Pat. No. 4,922,456 by Naddor et al. discloses a method which appears to lead into a somewhat similar direction, though it is mainly directed to preventing the wear out of a nonvolatile memory. The Naddor patent describes a method where data is written into a memory with a plurality of memory locations by first writing sufficient information into a double buffer comprising at least two memory locations to reconstruct the writing operation. Then, a flag is set to indicate that the information in the double buffer is accurate. The write operation is then performed, followed by the clearing of the flag. Finally, the two (or more) memory locations are moved through the memory to achieve the desired wear out prevention.
Based on the above, it is the general object of the present invention to provide a protection approach within the smartcard environment which approach is comparable to the data integrity mechanisms used in xe2x80x9clargexe2x80x9d database and transaction systems. More detailed, the main and foremost object of the present invention is to provide data integrity and protection against data loss or corruption both on the smartcard and in any associated data base.
A further, more general object is to guarantee the continued usability of a smartcard despite any previous interruption of a transaction to or from this smartcard, no matter what caused the interruption.
The solution according to the present invention is, in brief, to apply an xe2x80x9cadapted atomicity approachxe2x80x9d to the smartcard environment. The present invention shows a way how to adapt and use an atomic approach for smartcard transactions, i.e. for transaction between an external database and a smartcard.
As detailed in the appended claims, the present invention can be described as incorporating two essential features, which, in combination, can be considered to be the gist of the invention. One feature, in brief, is the provision and use of an internal trigger mechanism on the smartcard. The second essential feature, again in brief, is the provision and use of a so-called vector reference swapping scheme for data handling on the smartcard during the transaction.
Another feature contributing to the present invention is the use of a state-oriented scheme which sets the smartcard always either into the old state before a command was sent to the card, or into the new state which was envisaged to be achieved.
There are further features detailed in the claims. A particular interesting one may be considered the novel approach to select a particular granularity of the transaction processes, an approach appearing quite suitable for the smartcard environment. It may further encompass a recovery mechanism residing outside the smartcard, being appropriately authorized, and using suitable cryptographic means.
Another feature of the novel approach according to the invention is the use of a xe2x80x9cspare recordxe2x80x9d within the transaction process. This spare record may be seen as part of the recovery mechanism, allowing to recover the correct data whenever an interrupt occurs during the transaction.
To extend atomicity protection mechanisms to smartcards within the boundaries of their above described constraints results in an unmatched security of an appropriately equipped smartcard processing system. In the presently available systems, a new transaction cannot be started when the smartcard was left in a inconsistent state by a previous transaction; thus it usually becomes unusable which in turn may result in considerable trouble for the owner or user. If, however, a smartcard system is equipped with mechanisms according to the invention, which mechanisms allow to detect and recover from failure during a previous transaction, such a system has a significant advantage over a smartcard system without these mechanisms.
The following concentrates on an application which uses the vector reference swapping method, briefly mentioned above. A general mechanism is proposed how to commit the index values of the records.
Since the invention will be, to a large extent, implemented in software, there is more than one programming method, including a variety of data and control structures, which can embody the invention. An example shall be given below as a preferred embodiment of the invention according to the general inventive concept outlined above.
In principle, the present invention addresses atomicity on smartcards in general and is not limited to any particular granularity. However, to be able to describe and progressively build up a broad spectrum of mechanisms addressing the issue at any level, the description shall start at the bottom, with an atomicity scope of single file records on one card, meaning data records or control headers in the ISO sense, and one single card command.
When dealing with atomicity, a first parameter that needs definition is the granularity of the mechanism proposed. In classical transaction systems, some mechanisms address the atomicity of individual records (e.g. duplicated atomic stable storage), individual files (e.g. shadow paging), sets of files on the same computer system (e.g. WAL), or set of files across multiple systems (e.g. TPCP).
To break the problem and its explanation down, the whole complex shall be described in several steps:
The WAL (Write Ahead Log)
Normal Operation
Recovery and Distributed Transactions
Different Granularities, and
Parallelism (for future cards).
The smartcard operating system devotes a small area of its nonvolatile memory (NVM, implemented by EEPROM or FLASH technology) to atomicity protection as Write Ahead Log. That area may be managed as any typical WAL in a classical operating system. Given the storage limitations of smartcards, the following design should be the minimum.
Within the WAL area, the operating system devotes one location, typically a 32-bit word or page writeable in one memory cycle, to an atomic transaction flag. This flag will at any time contain one of three values:
EMPTY (the default value for the NVM technology),
ABORTED (meaning an atomic transaction is in progress), or
COMMITED (meaning it completed its real work but still needs to update the original data with the new values).
Next, the WAL contains a command buffer area capable of holding the largest command the card may possibly receive from its interface.
Finally the WAL must contain a data area. The data area must have room for original data (so a transaction can be backed up to its start point as if it never happened) and updated data (so a transaction can be rolled forward to completion if it reached its end point but did not have time to update the original data before a failure happened).
Classical atomic techniques allocate this data space either in the WAL area itself (in-WAL) or within the normal data space (in-file), with the WAL containing just pointers to the data records. Since space is usually scarce on a smartcard, it is preferable to leave original data where it is and store in the WAL just pointers to it.
Thus the WAL data area must contain a large enough vector of pointers to point at the largest set of records that any atomic transaction command will ever update on the cardxe2x80x94say N records. Each such pointer must of course include some file and record identification tag, as is usual in smartcard file formats, to allow the card software to know what is stored where.
For the update data, both in-WAL and in-file designs are possible. The choice of which one to apply is a matter of which one requires less space on the given card.
If the particular smartcard at hand contains many files with varying record sizes, but any particular atomic transaction updates only a small fraction of these files, then enough storage must be allocated in the WAL to contain only the largest number (N) of largest size records that any atomic transaction command will ever update at once (in-WAL update). Alternatively, if the card contains few files, or most files do get affected by most atomic transactions, then spare records and an associated mechanism to link them may be allocated within each file (in-file update). This latter approach should in general be the preferred one, given typical smartcard file structures, especially in the future, as spare records might be available in every file by design. In this latter case, the WAL need only contain pointers to the particular spare records updated by the ongoing transaction.
When a card is powered up, it checks the atomic transaction flag. If the flag is set to the distinguished value ABORTED, the card concludes that some earlier atomic transaction was interrupted and the card needs rollback recovery. It may post this condition to its interface and will in any case refuse any command from that interface with a corresponding error code, except recovery commands of course (see below). Another failure during this process cannot make things worse since the transaction was aborted anyway.
If the flag is set to COMMITTED, the card deduces that some transaction was interrupted before it could update all the original file records it meant to, but at least it had finished computing the new values of these records and these can thus be found either in the WAL itself or in spare file records pointed to by the WAL. The card thus proceeds to roll the old transaction forward, i.e. to make the old records become the new ones either by overwriting the old ones in place (in-WAL updates) or by linking the new ones from the spare list to the real files and returning the original ones from the file to the spare list (in-file updates). Either way, when all actual updating is completed, the card resets the flag to the default EMPTY state and proceeds as below. Another failure during this latter operation and before the EMPTY stage cannot break things since all new updates are in the WAL or the spare records listed in the WAL.
If the flag is found EMPTY at power-on, the card will accept an incoming command and analyze it to decide whether it belongs to the class needing atomic protection or not. If not, meaning the particular command does presumably not update anything on the card, the command may be executed right away. If yes, the card will start by copying the command into the WAL command buffer and setting the atomic transaction flag to ABORTED, meaning the transaction is starting and busy computing the new values of the updated records. If a failure occurs during that time, the transaction must be rolled back, leaving all original data unaffected.
As soon as the transaction has computed all new record values and updated them in the WAL or in the spare records, but before updating any original file, it marks the WAL flag as COMMITTED, meaning the real work is done but some storage copying and housekeeping is still needed. When that stage is finally reached and all original data is updated, the card clears the WAL flag to the EMPTY state, thus indicating that the card has returned to a restive operational state, awaiting the next command.
Given the above description, recovery operation in case of failure should be clear. While the card WAL flag is in EMPTY state, all is in order and no recovery is needed. If the flag is found in COMMITTED state, some storage copying and housekeeping are necessary, but the card can take care of it internally. If the flag is found in ABORTED state, the condition must be notified or reported by an error code to the external environment. From a card point of view, there is little to do but reset the flag to EMPTY. However, the aborted transaction may have been a distributed transaction involving external computing elements where some undoing may be needed, e.g. a money transfer between the card and its environment (perhaps another card) in either direction may have been interrupted after the environment committed it, but before it could tell the card to commit it, in which case some money clearly got lost or duplicated, and outside intervention is required to reconcile the distributed transaction.
To allow such reconciliation, it must be possible to issue a recovery command against the smartcard to find out which command was being executed when the failure occurred. To this end, an authorized outside agent must be allowed to read a (possibly encrypted) copy of the WAL command buffer. It is then up to the application protocol and outside the scope of what shall be described here to include enough information in that command to allow the authorized application owners to reconcile the overall distributed transaction, for instance by matching some transaction id between the aborted command on the card and some other record it may have seen or will see from some other terminal or card which was involved in the same transaction.
This may make the smartcard unusable until outside intervention can take place, which may require going to some specially authorized online terminal. This is however unavoidably required by the application semantics since it is not possible to know in what state the card is in general, and one cannot run the risk of resuming normal operation before insuring consistency of the card content.
The description so far assumed that the scope of a transaction was one single card command. In reality, some commands may go through several unrelated steps so they really equate to a sequence of commands. This can clearly be realized by running through several cycles of the above EMPTY-ABORTED-COMMITTED-EMPTY scenario.
Conversely, some transactions may straddle several card commands. That could be supported by allowing selected external commands to start and end transactions explicitly and maintaining several WALs such as the one used so far inside the card, so none of them can commit before the external card environment says so. This would clearly be beneficial to and help ease recovery of scenarios such as the distributed recovery one just described.
More interestingly, the scenario here described so far is such that the card can engage in a single command at a time. If a failure aborts that command and external intervention is needed, a user may be deprived of his/her card for a while. This may be fine for single-application scenarios. However, more and more multi-application cards appear on the market and there is no reason to block a whole card just because one single application is hung up needing recovery. In such cards, a different WAL file may be maintained for each application, so that the failure of one does not prevent the use of the others.
This latter scenario can be generalized to future cards, where several commands to different card applications may be issued in parallel and the card may, or in fact, will need a multi-tasking operating system. In such a case, multiple WAL files should also be maintained. Then, individual files and even records that may be shared across applications will need to carry locks to make sure applications cannot conflict with one another in updating files.
Since multiple WAL files and locks appear to be beyond the needs of today""s applications and, perhaps, the capabilities of today""s technology, a more xe2x80x9cclassical casexe2x80x9d shall be addressed in the following.
The fact today is that simple smartcards will not even have sufficient room for one single WAL. In such cases, at the very least a degenerate WAL is needed that contains just the flag and the ongoing command. Updating may be done in place, realizing of course that transactions are then not recoverable without outside intervention since data will get clobbered in case of failure. Having at least the WAL flag and command would however cause the card to fail in a known safe way, alert the user to contact a maintenance authority, and allow resetting the card in a suitable way depending on what command got interrupted. Hand-held readers should refrain from issuing atomic commands against card applications designed with such a degenerate WAL because they would invariably block the card and require outside intervention every time the card is pulled out before an operation can complete. If atomic commands are unavoidable, then a minimal number of spare records must be allocated in critical files to allow recovery without outside intervention.
A WAL will of course be written more often than anything else, e.g. the flag at least three times per transaction. This could be a problem with certain older EEPROM technologies where the number of write cycles is limited to some 10,000, meaning no more than some 3000 transactions could be carried out before the card may become unwriteable. This limitation is however rapidly becoming a concern of the past since latest technologies allow close to 100,000 write cycles, thus allowing 30,000 transactions over the lifetime of the card, which is typically a few, say two or three, years. This should allow around 30 or more transactions per day for a couple of years, which few cards are likely to reach in practice.
After these more general remarks, an embodiment of the invention shall be described in the following with reference to the drawings in which